#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<string>
#include<unordered_set>
#include<queue>
using namespace std;
class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string> as;
        unordered_set<string> hash(bank.begin(), bank.end());
        string change = "ACGT";
        queue<string> aq;
        if (!hash.count(endGene))
            return -1;
        if (startGene == endGene)
            return 0;
        aq.push(startGene);
        as.insert(startGene);
        int ret = 0;
        while (aq.size())
        {
            ret++;
            int sz = aq.size();
            while (sz--)
            {
                string w = aq.front();
                aq.pop();
                for (int i = 0; i < 8; i++)
                {
                    for (int j = 0; j < 4; j++)
                    {
                        string tmp = w;
                        tmp[i] = change[j];
                        if (hash.count(tmp) && !as.count(tmp))
                        {
                            if (tmp == endGene)
                                return ret;
                            aq.push(tmp);
                            as.insert(tmp);
                        }
                    }
                }
            }
        }
        return -1;
    }
};